package Class005;

import Utils.ArrayUtils;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        testSearch();
    }

    //基本二分搜索
    //若数组无序，或者有重复元素，会出错
    //重复元素只能确定是否存在
    //无重复元素可以确定其位置
    public static boolean basicBS(int[] arr, int target) {
        int L = 0, R = arr.length - 1, mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == target) return true;
            if (arr[mid] > target) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return false;
    }

    //找到数组中 <= target 的 最右边的元素
    public static int findNearestRight(int[] arr, int target) {
        int L = 0, R = arr.length - 1, index = -1, mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] <= target) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

    //找到数组中 >= target 的 最左边的元素
    public static int findNearestLeft(int[] arr, int target) {
        int L = 0, R = arr.length - 1, index = -1, mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] >= target) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

    public static boolean bruteSearch(int[] arr, int target) {
        for (int j : arr) {
            if (j == target) return true;
        }
        return false;
    }

    public static int bruteNearestLeft(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= target) return i;
        }
        return -1;
    }

    public static int bruteNearestRight(int[] arr, int target) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= target) return i;
        }
        return -1;
    }

    public static void testSearch() {
        int amount = 100, max = 100;
        int errTime = 0;
        int testTime = 100000;
        boolean error = false;
        int[] arr = ArrayUtils.generateArray(amount, max);
        Arrays.sort(arr);
        for (int curR = 1; curR <= testTime; curR++) {
            if (curR % 10 == 0) {
                //10轮更新一次
                arr = ArrayUtils.generateArray(amount, max);
                Arrays.sort(arr);
            }
            int target = (int) ((Math.random() * max + 1) - (max >> 1));
//            boolean myAns = basicBS(arr, target);
//            boolean stdAns = bruteSearch(arr, target);
//            int myAns = findNearestLeft(arr, target);
//            int stdAns = bruteNearestLeft(arr, target);
            int myAns = findNearestRight(arr, target);
            int stdAns = bruteNearestRight(arr, target);
            if (myAns != stdAns) {
                error = true;
                errTime++;
                System.out.println("curRound:" + curR + " has error...");
                System.out.println("Array:");
                System.out.println(Arrays.toString(arr));
                System.out.println("Target element:" + target);
                System.out.println("My ans(pos):" + myAns);
                System.out.println("std ans(pos):" + stdAns);
            }
        }
        if (!error) System.out.println("All clear.");
        else
            System.out.println("Accuracy:" + (1.0 * (testTime - errTime) / testTime));

    }
}
